import java.util.ArrayList;
import java.util.Scanner;

public class HeapSort {
    public static void main(String[] args) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        Scanner in = new Scanner(System.in);
        String l = in.nextLine();
        Scanner sc = new Scanner(l);
        while(sc.hasNext()) {
            array.add(sc.nextInt());
        }
        Integer[] arr = new Integer[array.size()];
        arr = array.toArray(arr);
        sort(arr);
        for (Integer integer : arr) {
            System.out.print(integer + " ");
        }
    }

    public static void sort(Integer[] array) {
        int cnt = 1;
        //1.构建大顶堆
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(array, i, array.length-1);
            System.out.println("第"+(cnt++)+"次：");
            for (Integer a : array) {
                System.out.print(a+" ");
            }
            System.out.println();
        }
        System.out.println("----------------------------");
        //2.调整堆结构+交换对顶元素与末尾元素
        for (int i = array.length-1; i > 0 ; i--) {
            swap(array, 0, i); //将堆顶元素与末尾元素进行交换
            adjustHeap(array, 0, i);
            System.out.println("第"+(cnt++)+"次：");
            for (Integer a : array) {
                System.out.print(a+" ");
            }
            System.out.println();
            System.out.println("+++++++++++++++++++++++++");
        }
    }

    public static void adjustHeap(Integer[] array, int i, int length) {
        System.out.println("i:"+i+"的值为："+array[i]+", length的值为："+length+", temp的值为："+array[i]);
        int temp = array[i];
        for (int j = i*2+1; j < length; j=j*2+1) { //从i结点的左子结点开始，也就是2i+1处开始
            System.out.println("i节点: "+array[i]+" 的左子节点： "+array[j]);
            if (j+1< length && array[j] < array[j + 1]) { //如果左子结点小于右子结点，j指向右子结点
                j++;
            }
            if (temp >= array[j]) {
                break;
            }
            array[i] = array[j]; //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            i = j;
        }
        array[i] = temp; //将temp值放到最终的位置
    }

    public static void swap(Integer[] array, int a, int b){
        int temp=array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}
